Symmetric Tree
問題概要
左右対称な二分木かどうかboolで返せ、という問題 解法
BFSでrootの次のノード以降を2つの二分木として分けて、最後に片方の配列ともう片方の逆配列がイコールになるかどうかで判定 code:solution.cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
vector<vector<int>> vec_a = {};
vector<vector<int>> vec_b = {};
traverse(root->left, 0, vec_a, true);
traverse(root->right, 0, vec_b, false);
return (vec_a == vec_b);
}
void traverse(TreeNode* node, int level, vector<vector<int>>& vec, bool is_a) {
int val = (node) ? (node->val) : -999;
if (level < vec.size()) {
vec.at(level).push_back(val);
} else {
vec.push_back({val});
};
// TODO: -999指定はテストケース次第でコケる可能性あるのでもうちょっと別の方法を考えたい
if (is_a && val != -999) {
traverse(node->left, level+1, vec, is_a);
traverse(node->right, level+1, vec, is_a);
} else if (val != -999) {
traverse(node->right, level+1, vec, is_a);
traverse(node->left, level+1, vec, is_a);
};
}
};